The present invention relates to a method and apparatus for detecting when a collision occurs between two or more binary data signal packets in a communication network.
Two communication technologies are in general use, circuit switching and packet switching. Communications over the switched public telephone line are illustrative of the circuit switching technique, and the Ethernet system is typical of the packet switching technique.
The circuit switching technique establishes a connection between two terminals only when a message is to be transmitted. However, because the time required to establish a connection may be very large compared to the actual time of a communication, especially in the case of a short communication, this technique is slow, inefficient and expensive.
In contrast, the packet switching technique maintains the communications connection but transmits the message in the form of packets of binary information. Short communications are transmitted by a single packet while longer or bursty communications are transmitted by a series of packets. Computer communications lend themselves to packet switching techniques because computer communications are characteristically in the form of short bursts of binary information.
The packet is typically divided into two primary sections, the header and the data, each of which has a different purpose. The header is the portion of the packet which is initially received and contains such information as the address to which the packet is to be sent, the address of the sender of the packet and other information that the particular system requires. Following the header is the data section where the substance of the communication is contained either wholly for a short communication, or partially for a longer communication. The packet may include an additional section which follows the data section which contains information relating to error checks or to packet linking. Packets typically are about 60 microseconds in duration. Data rates in the Ethernet system, for example, are 10 Megabits/second so that a single bit has a pulse width or duration of 100 nanoseconds and a packet contains about 6,000 bits.
In a typical packet switching system numerous terminals are connected to the same communication network and can access the network at the same time. As a result, it is possible that packet collisions will occur because more than one terminal transmits a packet at the same time. When a collision of packets is detected, an instruction is sent to retransmit the original data so that another attempt may be made to receive the packet without a collision. If a collision of packets is not detected, the information transmitted is lost since the signal received is unintelligible as it is a sum of the overlapping packets.
Numerous techniques are known in the art for detecting a data collision. Ordinarily, these techniques are implemented at each terminal that is transmitting a data packet. In U.S. Pat. No. 4,063,220, an exclusive OR gate at a signal transmitter compares the transmitted signal with the signal present on the communication cable and aborts transmission when they are not the same. Another technique is to monitor the DC level of the signal received from the communication line and, if this level is higher than a specified thereshold, assume there is a data collision. Alternatively, as disclosed, for example, in U.S. Pat. No. 4,282,512, the receiver can look for data transitions that occur at timings different from those expected for the received data.
U.S. Pat. No. 4,561,091 discloses a data communications receiver with a collision detection circuit for comparing a signal from a timing circuit with the received data signal. The receiver produces a collision detection signal when the received data signal fails to change within the duration of the output signal from the timing circuit which is set equal to the longest data signal interval.
U.S. Pat. No. 4,560,984 discloses a method for detecting the collision of data packets in which a signal pulse, having an amplitude much larger than a data pulse, is substituted for the initial bit of the packet. The receiver tests for a pulse much larger than a data pulse. If two large signal pulses are received within a time period less than or equal to the sum of the duration of the packet and the time period between packets, a collision has occurred.
However, the above methods do not detect collisions for certain conditions. For example, the above methods do not detect the collision of two signals which arrive at the receiver at approximately the same time. In addition, the above methods do not always detect collisions that may arise involving an attenuated signal. In optical communication systems, it has been found that up to a 26 dB loss (i.e. 99.7% decrease) of optical power may occur between the signal transmitted and the signal received. This loss of power may arise due to the length of transmission and the connectors or repeaters the signal passes through. In some cases of collision, the amplitude difference between two attenuated signals may be as much as 8 dB. This difference is so great that the smaller signal has little effect on the larger signal and the collision is undetectable by current collision detection techniques. These problems of detecting attenuated signals are increasing as communication systems switch to optical fibers.
U.S. Pat. No. 4,701,909 discloses a method for detecting collisions by using fixed Hamming weight sequences in the preamble of the data packet. If two packets collide, the received sequence presumably would be altered enough that a sequence weight violation could be detected.
U.S Pat. No. 4,562,582 discloses a method for detecting collisions by detecting certain code rule violations in a "Double Manchester" code sequence. Manchester code is a simple mapping of binary data into coded data at rate of 1 to 2 (i.e., each symbol of binary data is mapped to two symbols of coded data). Typically a 1 bit is mapped to 01 and a 0 bit is mapped to 10. Thus, a symbol pair having a positive going transition between the symbols is associated with the 1 bit and a symbol pair having a negative going transition is associated with the 0 bit. Since each symbol pair has a zero value and a one value, Manchester coding provides run-length limiting and zero/one balancing. A Double Manchester code sequence is one in which the Manchester encoder is applied twice to the data in the packet so that binary data is mapped into coded data at a rate of 1 to 4. While the method of the '582 patent detects some code rule violations, it does not detect all possible code rule violations, is unnecessarily complicated and involves a highly redundant encoding (i.e., 1 to 4) of the data.